import math
import random


def cmp(a, b, key):
    key_a, key_b = key(a), key(b)
    if key_a > key_b:
        return 1
    elif key_a < key_b:
        return -1
    return 0


def rank(sequence, value, key):
    count = 0
    for each in sequence:
        if cmp(each, value, key) < 0:
            count += 1
    return count + 1


def subset_by_range(s, a, b, key):
    subset = []
    for each in s:
        if cmp(a, each, key) <= 0 and cmp(each, b, key) <= 0:
            subset.append(each)
    return subset


def _lazyselect(s, k, key, r_exp=3 / 4):
    n = len(s)
    r_size = n ** r_exp
    r = random.choices(s, k=math.floor(r_size))
    r.sort(key=key)
    x = k * n ** (r_exp - 1)
    l = max(math.floor(x - math.sqrt(n)), 1)
    h = min(math.floor(x + math.sqrt(n)), len(r))
    a, b = r[l - 1], r[h - 1]
    rank_s_a, rank_s_b = rank(s, a, key), rank(s, b, key)
    if k < rank_s_a or k > rank_s_b:
        return None
    p = subset_by_range(s, a, b, key)
    if len(p) >= 4 * r_size:
        return None
    p.sort(key=key)
    return p[k - rank_s_a]


def lazyselect(sequence, k, key=None):
    if not 0 < k <= len(sequence):
        raise ValueError("Invalid k")
    if key is None:
        def default_key(x):
            return x
        key = default_key

    ret = _lazyselect(sequence, k, key=key)
    while ret is None:
        ret = _lazyselect(sequence, k, key=key)
    return ret


def median(sequence, key=None):
    return lazyselect(sequence, (len(sequence) + 1) // 2, key=key)


if __name__ == '__main__':
    # s = list(range(1, 100))
    # random.shuffle(s)
    # print(s)

    a = list(range(1, 100))
    b = list(range(1, 100))
    random.shuffle(a)
    random.shuffle(b)
    a[5] = None
    s = list(zip(a, b))
    print(s)

    # _k = 1
    # print(f'k = {_k}:', _lazyselect(s, _k))
    print(median(s, key=lambda x: x[1]))
